Desigualdade de Kraft
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Junho de 2016) |
Esta página ou se(c)ção precisa ser formatada para o padrão wiki. (Junho de 2016) |
As referências deste artigo necessitam de formatação. (Junho de 2016) |
A Desigualdade de Kraft é um importante teorema da Teoria de Códigos e Teoria da Informação usado para verificar se um código é livre de prefixo, ou seja, se todas as palavras-código são folhas na representação em árvore.
Definição
[editar | editar código-fonte]Em codificação de fonte, é necessário que todo código seja unicamente decodificável. Porém, ter esta condição como verdadeira muitas vezes não é o suficiente para uma decodificação prática, uma vez que, se o código não for livre de prefixo, mesmo sendo unicamente decodificável, há um acréscimo computacional no algoritmo de decodificação. Por esse motivo, é interessante uma codificação livre de prefixo, de forma que a decodificação possa ser instantânea.[1]
Assim vemos que, para uma boa codificação de dados, é necessário impor restrições na estrutura de um código instantâneo de comprimento variável de modo a garantir a unicidade da decodificação.
A Desigualdade de Kraft estabelece a condição necessária e suficiente de existência de um código instantâneo formado por palavras de comprimento variável, que é:
,
onde é o número de símbolos do alfabeto do código, o total de palavras-código e é o comprimento associado à i-ésima palavra-código.
Demonstração
[editar | editar código-fonte]Provamos a desigualdade de Kraft usando um raciocínio simples baseado na árvore de codificação.
Consideremos uma árvore r–ária onde cada nó tem r descendentes. Suponhamos ainda que cada ramo representa um símbolo da palavra-código. Por exemplo, os r ramos que partem da raiz da árvore representam os r possíveis valores do primeiro símbolo da palavra-código. Cada palavra-código corresponde a uma folha da árvore. O percurso entre a raiz e uma dessas folhas identifica os símbolos que fazem parte da palavra-código, conforme mostrado na Figura 1, para o caso binário .
A condição do código ser livre de prefixo implica que nenhuma palavra-código seja ancestral de qualquer outra palavra-código na árvore, ou seja, um ramo não pode ser uma palavra-código, somente as folhas podem exercer esse papel. Assim, cada palavra-código elimina os seus descendentes como possíveis palavras-código. Seja o comprimento da palavra mais longa do código. Consideremos todas as folhas ao nível máximo da árvore, como visto na Figura 2. Algumas folhas são palavras-código, enquanto outras são descendentes de palavras-código.
Qualquer palavra código terá descendentes no nível máximo, assim o número total de nós desse conjunto deverá ser inferior ou igual a . Somando essas contribuições, temos:
.
Simplificando, obtemos
,
que é a desigualdade de Kraft, conforme definimos na primeira seção.
Por outro lado, dado um conjunto de comprimentos de palavras-código que satisfazem a desigualdade de Kraft, é sempre possível construir uma árvore semelhante à da Figura 1, de modo a se obter um código livre de prefixo cujas palavras têm os comprimentos especificados.[2]
Referências
- ↑ Moser, Stefan M.; Chen, Po-Ning (2012). A Student's Guide to Coding and Information Theory. New York: Cambridge
- ↑ Figueiredo, Mário T. A. «Elementos de Teoria da Informação» (PDF). Consultado em 12 de agosto de 2016